#include <vector>
#include <stack>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution
{
public:
    int kthSmallest(TreeNode *root, int k)
    {
        // 迭代的中序遍历: 左-根-右
        int kth = 0;               // 记录当前是第几个节点
        TreeNode *cur = root;      // 当前节点
        stack<TreeNode *> st;      // 辅助栈
        while (cur || !st.empty()) // 当当前节点不为空或者栈不为空时
        {
            while (cur) // 一直往左走, 去找左子节点
            {
                st.push(cur);
                cur = cur->left;
            }
            // 当前节点为空, 说明左子节点已经走到头了, 开始出栈
            cur = st.top(); // 取出栈顶节点， 即当前节点
            st.pop();       // 出栈
            ++kth;          // 当前节点计数加1
            if (kth == k)   // 找到第k个节点
                return cur->val;
            cur = cur->right; // 左子节点走到头了,主节点出栈后, 开始遍历右子节点
        }
        return -1;
    }
    // 递归的中序遍历: 左-根-右
    void inorder(TreeNode *root, vector<int> &res)
    {
        if (!root)
            return;
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
};